#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    void quickSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int l = left, cur = left, r = right, k = nums[rand() % (right - left + 1) + left];
        while (cur <= r)
        {
            if (nums[cur] < k)swap(nums[cur++], nums[l++]);
            else if (nums[cur] > k)swap(nums[cur], nums[r--]);
            else cur++;
        }
        quickSort(nums, left, l - 1);
        quickSort(nums, r + 1, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};